package org.labuladong.动态规划算法.一维DP;

import java.util.Scanner;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-14:48
 * @Description:
 *
 * 你是⼀个专业的⼩偷，计划偷窃沿街的房屋。
 * 每间房内都藏有⼀定的现⾦，影响你偷窃的唯⼀制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同⼀晚上被⼩偷闯⼊，系统会⾃动报警。
 * 给定⼀个代表每个房屋存放⾦额的⾮负整数数组，计算你不触动警报装置的情况下，⼀夜之内能够偷窃到的最⾼⾦额。
 * 示例 1：
 * 输⼊：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋（⾦额 = 1)，然后偷窃 3 号房屋（⾦额 = 3)。
 *  偷窃到的最⾼⾦额 = 1 + 3 = 4。
 *
 * @version: 1.0
 */
public class LC_198打家劫舍DP {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
//		int[] nums = {1,2,3,1};
		int[] nums = new int[0];
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			nums = new int[n];
			for (int i = 0; i < n; i++) {
				nums[i] = sc.nextInt();
			}
			System.out.println(rob(nums));
		}

	}

	public static int rob(int[] nums) {
		// 1. 确定dp数组和下标的含义
		// dp[i]：表示前i个房屋能偷窃到的最高⾦额为dp[i]
		// dp[1] = nums[0]
		// dp[i] = dp[i-2]+nums[i-1] or dp[i-1]

//		int[] sum = new int[nums.length+1];
//		sum[0] = 0;
//		sum[1] = nums[0];
//		int res = -1;
//
		// 改写成dp
		int[] dp = new int[nums.length+1];
		dp[1] = nums[0];
		int res = nums[0];
		for (int i = 2; i <= nums.length; i++) {
			dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i-1]);
			res = Math.max(res, dp[i]);
		}

		return res;
	}

}
